\documentclass[a4paper,UTF8,noindent,10pt]{ctexart}

\usepackage {graphicx}
\usepackage {paralist}
\usepackage {marginnote}
\usepackage {amsmath}
\usepackage {tikz}
\CTEXsetup[format={\Large\bfseries}]{section}
\usepackage[top=1in, bottom=1in, left =1in, right=1in]{geometry}

\pagestyle{plain}

\newcommand{\myPara}[1]{
	\paragraph {#1}
	\hangindent=5em \hangafter=1
	\quad\\
}

\usepackage{listings}
\usepackage{color}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
  language=c,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=right,
  numberstyle=\small\color{green},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true,
  tabsize=4, 
  escapeinside=``
}

\begin {document}

\section {luogu-P1010 幂次方}

\myPara {题目描述}
任何一个正整数都可以用$2$的幂次方表示。例如
$$137=2^7+2^3+2^0 $$ 
同时约定方次用括号来表示，即$a^b$ 可表示为$a(b)$。
由此可知，$137$可表示为：
$$2(7)+2(3)+2(0)$$
进一步：
$$7= 2^2+2+2^0$$ ($2^1$用2表示)，并且
$$3=2+2^0$$ 
所以最后$137$可表示为：
$$2(2(2)+2+2(0))+2(2+2(0))+2(0)$$
又如：
$$1315=2^{10} +2^8 +2^5 +2+1$$
所以$1315$最后可表示为：
$$2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)$$


\myPara {输入格式} 
一个正整数 $n(n \leq 20000)$。 
\myPara {输出格式} 
符合约定的$n$的$0,2$表示(在表示中不能有空格) 
\myPara {样例} 
输入样例\#1: \\
1315 \\
输出样例\#1: \\
$2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)$

\myPara {解析} 
根据本题描述，容易想到计算机内部是用二级制来表达一个整数的，例如$137H = 10001001B$。
如下图所示，假设在内存中用8个位（bit）来表示137这个数字，从左到右依次为第7位到第0位。
因为137这个数字中含有$2^7$，所以二进制第7位上数字为1。又因为这个数字中不包含$2^6$
这个数字，所以第6位上数字为0。
\newline
在C语言中，可以使用位运算$a\&(1<<i)$来判断整数a的第i位上的数字是否为1。$(1<<i)$是一个
移位操作，把1向右移动i位，就得到了一个i位上为1、其他位均为0的二进制数。\&是按位与(and)操作，
也就是用两个整数的对应二进制位进行逻辑与操作。逻辑与的规则是：如果进行操作的两个位均为1，则结果为1；
如果两个参与操作的二进制任何一个为0，则结果为0。

\begin{figure}[htbp]
\centering
\begin {tikzpicture}
\draw node at (0pt,  20pt) {bit7} ; 
\draw node at (30pt, 20pt) {bit6}; 
\draw node at (60pt, 20pt) {bit5}; 
\draw node at (90pt, 20pt) {bit4}; 
\draw node at (120pt, 20pt) {bit3}; 
\draw node at (150pt,20pt) {bit2}; 
\draw node at (180pt,20pt) {bit1}; 
\draw node at (210pt,20pt) {bit0}; 

\draw node[draw] (b7) at (0pt,  0) {1} ; 
\draw node[draw] (b6) at (30pt, 0) {0}; 
\draw node[draw] (b5) at (60pt, 0) {0}; 
\draw node[draw] (b4) at (90pt, 0) {0}; 
\draw node[draw] (b3) at (120pt, 0) {1}; 
\draw node[draw] (b2) at (150pt,0) {0}; 
\draw node[draw] (b1) at (180pt,0) {0}; 
\draw node[draw] (b0) at (210pt,0) {1}; 
\draw [->, dashed] (b7) |- (320pt, -80pt) node[fill=red!70!yellow] {第7位为1，表示 $2^7$}; 
\draw [->, dashed] (b3) |- (320pt, -60pt) node[fill=red!70!yellow] {第3位为1，表示 $2^3$}; 
\draw [->, dashed] (b0) |- (320pt, -40pt) node[fill=red!70!yellow] {第0位为1，表示 $2^0$}; 
\end {tikzpicture}
\caption{137的二进制表示}
\end{figure}


\myPara {代码} 
下面代码中out\_power函数，是用来计算并输出结果的。第8行，如果a为0，就只输出一个0。
如果a不为0，则输出下面的信息。使用第63行的for语句依次判断a的每一个二级制位是否为1，如果为1才输出，不为1则不输出。
其中第12行是判断这一位是否为1。如果不是第一个数字，则在输出数字之前要先输出一个加号。第16行到20行，如果不是第1位，
则递归调用out\_power输出幂的数字。

\begin{lstlisting}

#include <stdio.h>

void out_power(long a)
{
    int     i;
    int     first = 1;
    if (a==0) {
       printf("0");
       return;
    }
    for (i=63; i>=0; i--) {
        if (a & (1UL<<i)) {
            if (!first)
                printf("+");
            printf("2");
            if (i!=1) {
                printf("(");
                out_power(i);
                printf(")");
            }
            first = 0;
        }
    }
}

// `中文注释`
int main()
{
    long a;

    scanf("%ld", &a);
    out_power(a);
    printf("\n");

    return 0;
}


\end{lstlisting}

\end {document}






